CS 4311-1

Brief

In this course, we will look at a lot of fundamental problems that are solved daily around us, and we will study their solutions (that is, the methods or the algorithms), and show how to analyze the performance of the solutions. We will also introduce general techniques to help us design a good algorithm when we face a new problem.

Description

Course keywords: Algorithms, Design, Performance Analysis, Complexity, Correctness 一、課程說明 (Course Description) There are many problems around us, and they need some fast and good methods to be solved. For instance, (i) Suppose that we have been very lazy the last few weeks, and suddenly, we find that 10 homeworks A,B,C,D,E,..., J will be due next week. The homeworks have different deadlines, and some will be on Monday, some will be on Friday. We have an estimation of how fast we can finish each homework. Questions: Can we finish all of them? If so, which one should we do first, which one next? (ii) Suppose that our school has 100 landmarks (such as the library, the EECS building, the main gate, etc), and you want to design a system so that if a user enters any two landmarks (say, A and B), your system can immediately suggest a shortest route from A to B. Of course, you can find all the 100x100 routes by yourself, but it would be better if you can write a computer program to do it for you. Is there any efficient computer program for this problem? To solve a particular problem, there are usually many different methods. For instance, in Problem (i), we can try all possible arrangements of the homeworks A,B,C,D,E, ... and see if they can all be finished in time. However, we need to try 10! arrangements, and this would take a long time. On the other hand, if we want to finish all the homeworks, it seems that we should do the one whose deadline is nearest first, and then do the one whose deadline is second nearest, and so on. There may be other methods we can try. One question arises: Among all methods, is there one which is always faster and better than the others? In this course, we will look at a lot of fundamental problems that are solved daily around us, and we will study their solutions (that is, the methods or the algorithms), and show how to analyze the performance of the solutions. We will also introduce general techniques to help us design a good algorithm when we face a new problem. 二、指定用書 (Text Book) Introduction to algorithms, 2nd edition, the MIT press, 2001 by T. Cormen, C. E. Leiserson, and R. L. Rivest 三、參考書籍 (References) 1. Algorithms in C++, (or Algorithms in Java), by R. Sedgewick 2. The Art of Computer Programming, by D. E. Knuth 四、教學方式 (Teaching Method) Lectures and Tutorials (in English) 五、教學進度 (Syllabus) 　I. Mathematical Foundations 1. Introduction 　 2. Growth of Functions 3. Summations 4. Recurrences II. Sorting and Order Statistics 6. Heapsort 7. Quicksort 8. Sorting In Linear Time 9. Medians and Order Statistics III. Data Structures: Self Study IV. Advanced Design and Analysis Techniques 15. Dynamic Programming 16. Greedy Algorithms 17. Amortized Analysis V. Advanced Data Structures 19. Binomial Heaps 20. Fibonacii Heaps 21. Data Structures for Disjoint Sets VI. Graph Algorithms 22. Elementary Graph Algorithms 23. Minimum Spanning Trees 24. Single-Source Shortest Paths 25. All-Pairs Shortest Paths VII. Selected Topics 34. NP-Completeness 35. Approximation Algorithms 六、成績考核 (Evaluation) 5--6 assignments 0% 3 exams 100% ---------------------- Total 100% There are two formula for your final score: (1) 20 + (average of 3 exams) * 0.8 (2) (average of the best 2 exams) * 0.8 + (the worst one) * 0.2 Final score = Maximum of (1) and (2). 七、可連結之網頁位址 (Web links) www.cs.nthu.edu.tw/~wkhon/algo08.html 八、AI 使用規則 (Rule for Co-work with AI) Conditionally open; please specify how generative AI will be used in course output

Timetable

Remarks

非資工本系生請修習113下特別為資工輔系、雙主修、專長同學開設之同名課程。

Restrictions

資工系大學部3年級優先，第3次選課起開放全校修習

Compulsory

Elective

Cross Discipline

First Specialization

Second Specialization